\documentclass{article}

\usepackage{algorithmic}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{booktabs}

\begin{document}

\title{K-Nearest Neighbors}
\author{Geoffrey Ulman\\
        Homework 11\\
        CSI873}
\date{December 2011}
\maketitle

\section{Results}\label{Results}

The minimum testing error rate for k-nearest neighbors with uniform weights was \(0.241\) and occurred with \(k=4\). The minimum testing error rate for k-nearest neighbors with weights decaying by distance according to Equation \ref{decay} was \(0.217\) and occurred with \(k=7\).

\begin{equation}\label{decay}
w_i = \frac{1}{d \left( x_q , x_i \right)^2 + \epsilon } , \epsilon = 1
\end{equation}

The trend for larger k for both the uniform and decaying weight runs is shown on Figure \ref{plot1}. It indicates that the error rate of \(0.217\) obtained by the decaying weight knn classifier with \(k=7\) is actually the best performing for all \(k\) for this handwriting classification problem. Even including all training samples weighted by distance does not improve the error rate. In fact, with an error rate of \(0.410\) it is a significantly worse performer than the runs with small \(k\) values.

\begin{figure}
\centering
\includegraphics[width=0.9\textwidth]{KNNError.png}
\caption{Missclassification Error by K}
\label{plot1}
\end{figure}

\begin{table}
\caption{Uniform Weight Error}
\begin{center}
\begin{tabular}{llcc}
\toprule
K & Error & \multicolumn{2}{c}{95\% Confidence Interval} \\
\cmidrule(r){3-4}
& & Lower Bound & Upper Bound \\
\midrule
1 & 0.254 & 0.212 & 0.296 \\
2 & 0.266 & 0.223 & 0.309 \\
3 & 0.259 & 0.216 & 0.301 \\
4 & 0.241 & 0.200 & 0.283 \\
5 & 0.273 & 0.230 & 0.316 \\
6 & 0.280 & 0.237 & 0.324 \\
7 & 0.268 & 0.225 & 0.311 \\
\bottomrule
\end{tabular}
\label{error1}
\end{center}
\end{table}

\begin{table}
\caption{Decaying Weight Error}
\begin{center}
\begin{tabular}{llcc}
\toprule
K & Error & \multicolumn{2}{c}{95\% Confidence Interval} \\
\cmidrule(r){3-4}
& & Lower Bound & Upper Bound \\
\midrule
1 & 0.254 & 0.212 & 0.296 \\
2 & 0.244 & 0.202 & 0.285 \\
3 & 0.227 & 0.186 & 0.267 \\
4 & 0.234 & 0.193 & 0.275 \\
5 & 0.237 & 0.195 & 0.278 \\
6 & 0.229 & 0.189 & 0.270 \\
7 & 0.217 & 0.177 & 0.257 \\
410 & 0.410 & 0.362 & 0.457 \\
\bottomrule
\end{tabular}
\label{error2}
\end{center}
\end{table}


\begin{thebibliography}{9}

\bibitem{cpl}
  Tom M. Mitchell,
  \emph{Machine Learning},
  WCB McGraw-Hill, Boston,
  1997.

\end{thebibliography}

\end{document}
